package com.duoduo.双指针;

import com.duoduo.ListNode;

/**
 * @program: algorithm
 * @description: 回文链表234
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * <p>
 * 输入：head = [1,2,2,1]
 * 输出：true
 * <p>
 * 输入：head = [1,2]
 * 输出：false
 * @author: chaidl  ！
 * @create: 2022-04-08 15:39
 */
public class 回文链表234 {
	//  [1,2,3,2,1]  王甜甜
	public boolean isPalindrome(ListNode head) {
		//首先定义两个前后指针
		ListNode fast = head, slow = head;
		//快指针每次走两步，慢指针每次走一步
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		//在这里判断链表个数是否是偶数，如果fast等于Null就是偶数
		if (fast != null) {
			slow = slow.next;
		}
		//	将slow指针后面的链表进行反转
		slow = reverse(slow);
		//	将快指针指向头结点，一次遍历判断是否全部相等
		fast = head;
		while (slow != null){
			if (slow.val!=fast.val){
				return false;
			}
			slow=slow.next;
			fast=fast.next;
		}
		return true;
	}
	
	private ListNode reverse(ListNode head) {
		ListNode prev = null;
		while (head != null) {
			ListNode next = head.next;
			head.next = prev;
			prev = head;
			head = next;
		}
		return prev;
	}
}
